package org.streets.commons.match;

public class DstTree {
	
	DstNode root;
	int n;
	int max_b;

	public DstTree(int max_b) {
		root = null;
		n = 0;
		this.max_b = max_b;
	}

	/*
	 * dst_insert() - Inserts an item into the digital search tree pointed to by
	 * t, according the the value its key. The key of an item in the digital
	 * search tree tree must be unique among items in the tree. If an item with
	 * the same key already exists in the tree, a pointer to that item is
	 * returned. Otherwise, NULL is returned, indicating insertion was
	 * successful.
	 */
	public DstItem insert(DstItem item) {
		int key;
		int j, i, mask;
		DstNode p;
		DstNode next_p;

		key = item.key;
		next_p = root;
		if (next_p != null) {
			mask = 1 << (i = max_b - 1);/* Locate the insertion position. */
			for (;;) {
				p = next_p;
				if (p.key == key) {
					return p.item;
				} /* Item found. */

				/* Traverse left or right branch, depending on the current bit. */
				j = (key & mask) >> i;
				next_p = p.a[j];
				/* Empty position to insert at. */
				if (next_p == null) {
					/* Create a new node. */
					p.a[j] = new DstNode();
					p.a[j].a[0] = p.a[j].a[1] = null;
					p.a[j].key = key;
					p.a[j].item = item;
					/* Join the new node onto the tree. */
					// child_link=x;
					break;
				} /* Move to the next bit. */
				mask >>= 1;
				i--;
			}
		} else {
			/* Create a new node. */
			root = new DstNode();
			root.a[0] = root.a[1] = null;
			root.key = key;
			root.item = item;
		}
		this.n++;
		return null;
	}

	/*
	 * dst_find() - Find an item in the digital search tree with the same key as
	 * the item pointed to by `key_item'. Returns a pointer to the item found,
	 * or NULL if no item was found.
	 */
	public DstItem find(char key_item) {
		
		int i, j, key, mask;
		DstNode p;
		DstNode next_p;

		next_p = root;
		if (next_p != null) {
			mask = 1 << (i = max_b - 1);
			key = key_item;
			/* Search for the node with key `key'. */
			for (;;) {
				p = next_p;
				if (p.key == key) {
					return p.item;
				} /* Item found. */

				/* Traverse left or right branch, depending on the current bit. */
				j = (key & mask) >> i;
				next_p = p.a[j];
				if (next_p == null) {
					return null;
				}
				/* Move to the next bit. */
				mask >>= 1;
				i--;
			}
		}
		return null;
	}

	/*
	 * dst_find() - Find an item in the digital search tree with the same key as
	 * the item pointed to by `key_item'. Returns a pointer to the item found,
	 * or NULL if no item was found.
	 */
	public DstItem find_min(DstTree t) {
		int min_key;
		DstNode p;
		DstNode next_p;
		DstNode min_node = null;
		next_p = root;
		if (next_p != null) {
			min_key = 0xFFFFFFFF & 0xff; /* Note the sign bit. */
			for (;;) {
				p = next_p;
				if (p.key <= min_key) {
					min_node = p;
					min_key = p.key;
				}
				next_p = (p.a[0] != null) ? p.a[0] : p.a[1];
				if (next_p == null)
					return min_node.item;
			}
		}
		return null;
	}

	public void dump(DstNode p, int l) {
		int i;
		for (i = 0; i < 2 * l; i++)
			System.out.print(" ");
		if (p != null)
			System.out.println("" + (p.item).key + "");
		else {
			System.out.println("--");
			return;
		}
		if (p.a[0] == null & p.a[1] == null)
			return;
		this.dump(p.a[0], l + 1);
		this.dump(p.a[1], l + 1);
	}
}
